The spectral gap - the energy difference between the ground state and firstexcited state - is central to quantum many-body physics. Many challenging openproblems, such as the Haldane conjecture, existence of gapped topological spinliquid phases, or the Yang-Mills gap conjecture, concern spectral gaps. Theseand other problems are particular cases of the general spectral gap problem:given a quantum many-body Hamiltonian, is it gapped or gapless? Here we provethat this is an undecidable problem. We construct families of quantum spinsystems on a 2D lattice with translationally-invariant, nearest-neighbourinteractions for which the spectral gap problem is undecidable. This resultextends to undecidability of other low energy properties, such as existence ofalgebraically decaying ground-state correlations. The proof combinesHamiltonian complexity techniques with aperiodic tilings, to construct aHamiltonian whose ground state encodes the evolution of a quantumphase-estimation algorithm followed by a universal Turing Machine. The spectralgap depends on the outcome of the corresponding Halting Problem. Our resultimplies that there exists no algorithm to determine whether an arbitrary modelis gapped or gapless. It also implies that there exist models for which thepresence or absence of a spectral gap is independent of the axioms ofmathematics.
展开▼